package pro.softzhang.algo.lc200;

import pro.softzhang.algo.flag.difficulty.DRed;
import pro.softzhang.algo.flag.knowledge.KGraph;

import java.util.*;

@DRed
@KGraph
public class LC269_AlienDictionary {
    public static void main(String[] args) {

    }

    static class Solution {
        public String alienOrder(String[] words) {
            Map<Character, Set<Character>> graph = new HashMap<>();
            Map<Character, Integer> inDegrees = new HashMap<>();
            for (String word : words) {
                for (char ch : word.toCharArray()) {
                    graph.putIfAbsent(ch, new HashSet<>());
                    inDegrees.putIfAbsent(ch, 0);
                }
            }

            for (int i = 1; i < words.length; i++) {
                String w1 = words[i - 1];
                String w2 = words[i];
                if (w1.startsWith(w2) && !w1.equals(w2)) {
                    return "";
                }

                for (int j = 0; j < w1.length() && j < w2.length(); j++) {
                    char ch1 = w1.charAt(j);
                    char ch2 = w2.charAt(j);
                    if (ch1 != ch2) {
                        if(!graph.get(ch1).contains(ch2)) {
                            graph.get(ch1).add(ch2);
                            inDegrees.put(ch2, inDegrees.get(ch2) + 1);
                        }
                        break;
                    }
                }
            }

            Queue<Character> q = new LinkedList<>();
            for (char ch : inDegrees.keySet()) {
                if(inDegrees.get(ch) == 0) {
                    q.add(ch);
                }
            }

            StringBuilder sb = new StringBuilder();
            while (!q.isEmpty()) {
                char ch = q.remove();
                sb.append(ch);
                for (char next : graph.get(ch)) {
                    inDegrees.put(next, inDegrees.get(next) - 1);
                    if (inDegrees.get(next) == 0) {
                        q.add(next);
                    }
                }
            }

            return sb.length() == graph.size() ? sb.toString() : "";
        }
    }
}
